💻 Heap Sort for Lexicographic String Order

Visualize the Heap Sort algorithm rearranging words (strings) efficiently.

💻 Neha's Lexicographic Challenge

🎯 The Challenge:

Sort a list of words efficiently in **lexicographic (alphabetical) order** to improve search engine performance.

📋 Algorithm Requirement:

  • The sorting algorithm must be **Heap Sort** (Max Heap variant).
  • Comparison uses standard case-sensitive lexicographic order (e.g., "Banana" comes before "apple").
  • **Input:** N strings (words). **Output:** N sorted strings.

Problem Specifications

  • **Input:** Space-separated words (e.g., `kiwi grape fig Date apple Banana`)
  • **Constraint:** N ≤ 20 (for demo visualization limits)
  • **Output:** Sorted words (e.g., `Banana Date apple fig grape kiwi`)

Sample Input/Output

Input: banana pineapple mango chikoo jack star guava lemon tomato orange
Output: banana chikoo guava jack lemon mango orange pineapple star tomato

🔄 Heap Sort Strategy (Max Heap)

Key idea

  1. **Build Max Heap:** Arrange the array data structure into a Max Heap, where every parent node is lexicographically greater than or equal to its children.
  2. **Heapify:** Repeatedly swap the root (largest element) with the last element of the unsorted section of the array.
  3. **Extract Max:** Reduce the heap size by 1 and call **Max-Heapify** on the new root to restore the Max Heap property.
  4. Repeat until the heap size is 1. The array is now sorted.

Time Complexity

O(N log N)

Building the heap is $O(N)$. $N$ extractions, each $O(\log N)$.

Space Complexity

O(1)

It's an in-place sort. (Or $O(\log N)$ for recursion stack).

🔍 Step-by-Step Heap Sort Demo

Max 10 words for better visualization
Ready. Use controls below to start demo.

Current Array State

Click Start to run Heap Sort

Progress tracker

1. Initialize array and Max Heap properties
2. **Build Max Heap:** Call Heapify on all non-leaf nodes
3. **Sort Loop:** Max element (root) is found
4. Swap root with the last unsorted element
5. Reduce heap size and Max-Heapify the new root
6. Repeat until all elements are sorted

🎮 Practice Sorting Different Inputs

Enter words and press Sort Words

📊 Analysis & Key Takeaways

Comparison (String)

O(L)

Where L is the max length of a string. Total time is $O(N \cdot L \cdot \log N)$.

Stability

No

Heap Sort is generally **not stable** because of the swaps that occur when maintaining the heap property.

Key Advantages of Heap Sort

  • **Guaranteed** $O(N \log N)$ worst-case time complexity.
  • It's an **in-place** sorting algorithm (minimal extra memory).
  • Excellent for large datasets where consistency is key.